#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 

示例 1：

输入：nums = [1,2,0]
输出：3
示例 2：

输入：nums = [3,4,-1,1]
输出：2
示例 3：

输入：nums = [7,8,9,11,12]
输出：1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/first-missing-positive
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
//遍历一次数组把大于等于1的和小于数组大小的值放到原数组对应位置，然后再遍历一次数组查当前下标是否和值对应，如果不对应那这个下标就是答案，否则遍历完都没出现那么答案就是数组长度加1。
//TODO 那么就是从1 开始了 我擦这个是考研题
//[1,2,0]
// 2 1
//思路把 数组转换到下标0 对应1 1 对应2 那种

//还必须 算上一个数组的size()万一是 下标为0 对应1 然后一次类推
int firstMissingPositive(vector<int>& nums) {

    for (int i = 0; i <nums.size() ; ++i) {

        //[3,4,-1,1] 让 下标0 对应 1
        while (nums[i]>0&&nums[i]<=nums.size()&& nums[i]!=i+1){

            //防止有重复数一直循环我草啊啊啊啊啊
            if (nums[i]==nums[nums[i]-1])
                break;
           //现在0存的是1的值
          swap(nums[i],nums[nums[i]-1]);//这个刚好对应-1

        }


    }
    int i;
    for ( i = 0; i <nums.size() ; ++i) {
        if (nums[i]!=i+1)
            return i+1;

    }

    return i+1;
}